The technology described herein relates to methods of and apparatus for encoding and decoding data, and in particular to such methods and apparatus for use when compressing and decompressing texture data for use in computer graphics systems.
It is common in computer graphics systems to generate colours for sampling positions in an image to be displayed by applying so-called textures or texture data to the surfaces to be drawn. For example, surface detail on objects may be generated by applying a predefined “texture” to a set of graphics primitives (such as polygons) representing the object, to give the rendered image of the object the appearance of the “texture”. Such textures are typically applied by storing an array of texture elements or “texels”, each representing given texture data (such as colour, luminance, and/or light/shadow, etc., values) at a given location (position), and then mapping the texels onto the corresponding elements, such as (and, indeed, typically) a set of sampling positions, for the image to be displayed. The stored arrays of texture elements (data) are typically referred to as “texture maps”.
Such arrangements can provide relatively high image quality, but have a number of drawbacks. In particular, the storage of the texture data and accessing it in use can place, e.g., high storage and processing requirements on a graphics processing device (or conversely lead to a loss in performance where such requirements are not met). This is particularly significant for lower power, mobile, and handheld, devices that perform graphics processing, as such devices are inherently limited in their, e.g., storage, bandwidth and power resources and capabilities.
It is known therefore to try to encode such texture data in a “compressed” form so as to try to reduce, e.g., the storage and bandwidth burden that may be imposed on a graphics processing device when using textures.
It is common for texture compression techniques to use block-based encoding, i.e. arrangements in which the overall array of texture elements (the texture map) to be encoded is divided into an array of smaller blocks of texels (such as blocks of 4×4 texels), with each such block then being encoded (compressed), and decoded, separately. This can, e.g., help to make the decoding process more efficient, because the decoder, for example, may need to decode only one or a few of the encoded blocks to determine the value of a texel of interest, rather than the entire encoded texture.
Block-based texture compression techniques typically determine a reduced set or palette of colours (or other data) to be used for a given block of texels, and then store for each texture element (texel) in the block an index into the set or palette of colours, indicating the colour to be used for the texture element (texel) in question. This has the advantage that only an index, rather than a full, e.g. colour, value needs to be stored for each texel.
One known block-based texture compression technique is so-called block truncation encoding (BTC). In this technique the overall texture array (texture map) is subdivided into smaller blocks, e.g. of 4×4 texels, and a number (typically two) of base or primary colour values is determined for each such block, with each texel in the block being set to one of the base colour values. This saves on the data that has to be stored and accessed, but at a cost of lower image quality.
U.S. Pat. No. 5,047,853 describes an improved block truncation coding technique. In this technique, two base colours are again stored for each texel block, but two additional colours to be used for the block are also derived from those two base colours (e.g. by linearly blending those colours). In this way, four colours are provided as a “palette” for the texel block, but only two colour values need to be stored for the block. Each texel in the block is then encoded using two index bits, to indicate which of the four block “colours” should be used for the texel. This system provides improved image quality over basic block truncation coding, but requires more data per block.
There are other block-based texture compression schemes, such as S3TC, BC6 and BC7 that similarly divide the texture into blocks, then define two base “endpoint” colours for each block, form additional colours by interpolating between the two endpoint colours, and then use an index for each texel to select the colour for the texel from the resulting set of colours.
For example, in the S3TC texture compression format, a texture is represented as 4×4 texel blocks. For each block, two endpoint colors are determined, and two additional colors are formed through interpolation between the two endpoints. This results in a palette of four colors for the block that all lie on a straight line in the color-space. A texel index is then used, for each texel, to map the texel to one of the four colors. Each encoded block stores the two endpoint colors for the block and a grid of 4×4 texel indexes for the block.
The most complex step of these types of texture compression process is usually the selection of the two endpoint colors to use. This is usually done by determining a line in the colour space that the texel values can be projected on to. This line is usually derived by computing an average color and a direction vector for the texel block in question. The line in the color-space that the texels in the block are then projected on to is then determined to be the line passing through the average colour point and having the direction of the determined direction vector.
In these arrangements, the best direction vector to use is a vector that lies along the direction in the colour space along which the texels exhibit the greatest variance in their values (i.e. the dominant direction for the texel values in the colour space), and so is traditionally computed using the discrete Karhunen-Loewe Transform (KLT) (also known as Principal Component Analysis).
Thus, a standard method to compute the two endpoint colors to be used when encoding a block of texels (given the uncompressed texture, where every texel is represented, e.g. with an (R,G,B) color tuple, as the input) is as follows:                1. Compute an average color C across the block of texels to be encoded        2. For each texel, subtract the average color C from the texel's color value: T′=T−C        3. From the subtracted texel values in step 2, compute a covariance matrix M        4. Compute M's eigenvalues and eigenvectors, then keep the eigenvector V that represented the most energy. This can be done by computing the eigenvector corresponding to the largest eigenvalue, or by using the “Power Iteration” method to find the dominant eigenvector.        5. Define a parametric line in the color-space that passes through the average colour value C and has the direction of the determined eigenvector V, L=C+t*V        6. Project all the texels onto this line (i.e. determine, for each texel, the point on the line that is closest to that texel). This basically amounts to finding a parameter value t for the point on the line L that is closest to the texel: given a subtracted texel T′=T−C, the parameter can be computed as t=dot(V,T′)/dot(V,V), where dot( ) denotes the usual vector dot-product.        7. Find the highest and lowest points (values) on the line that the texels were projected on to. This basically amounts to finding the lowest (t_low) and highest (t_high) parameter values that resulted from the texels.        8. Then define the endpoint colors as being the highest and lowest points (values) on the line that the texels were projected on to. This basically amounts to defining: E1=C+t_low*V and E2=C+t_high*V        
After these two endpoint values have been computed, the, e.g. two, other colour values to use for the encoded block are computed by interpolation from these endpoint colours (e.g. as ⅓ E1+⅔ E2, and ⅔ E1+⅓ E2, respectively). Each texel is then assigned an index corresponding to which of the, e.g., four, colours for the block its colour value is closest to (for fast encoding, this can be done by just rescaling and quantizing the parameter values ‘t’ computed in step 6 above).
In this process, steps 1-4 make up the Karhunen-Loewe transform and the remaining steps make use of the KLT result to perform the actual texture compression.
Using the Karhunen-Loewe transform (and in particular steps 3 and 4 above) to determine the vector direction to use, while providing an accurate estimate of the desired dominant direction for the block of texels to be encoded, is computationally expensive, and prone to numeric instability and the requirement to handle special cases.
For example, when computing eigenvalues, it is necessary to solve a 3rd degree polynomial. Doing this analytically requires several expensive transcendental operations (cube-root, sine, cosine, arctan), and doing it numerically requires relatively complex methods (e.g. Jenkins-Traub) to ensure convergence in reasonable time.
Using a power iteration method to find the dominant eigenvector is simpler. However, this still requires picking a random vector, then repeatedly multiplying it with the covariance matrix until the resulting vector eventually converges to the dominant eigenvector. Care also needs to be taken to ensure that the repetition doesn't result in an overflow or underflow.
Special care is also needed to handle situations like uniform-colour blocks (which result in an all-zeroes covariance matrix; such a matrix has no eigenvectors), and blocks where there are two equally-dominant directions (multiplicity-2 eigenvalues).
This all means that while the existing techniques for deriving the endpoint colours to use when encoding a block of texels, and in particular for determining the direction of the line in the colour space to use when doing that, can accurately identify a good direction to use for this (namely the dominant direction (principal axis) of the texel values in the colour space), those existing techniques are computationally expensive and slow.
The Applicants believe therefore that there remains scope for improved techniques for estimating the dominant direction of a set (e.g. block) of texel values to be encoded (i.e. the direction along which the values of the texels being considered exhibit the greatest variance), and in particular when determining the, e.g., endpoint colours, to use when encoding texture data for use in a graphics processing system.
Like numerals are used for like features in the drawings (where appropriate).